A natural number is called k-prime if it has exactly k prime factors, counted with >multiplicity. A natural number is thus prime if and only if it is 1-prime.
Examples:
k = 2 -> 4, 6, 9, 10, 14, 15, 21, 22, …
k = 3 -> 8, 12, 18, 20, 27, 28, 30, …
k = 5 -> 32, 48, 72, 80, 108, 112, …
Task:
Given an integer k and a list arr of positive integers the function consec_kprimes (or >its variants in other languages) returns how many times in the sequence arr numbers >come up twice in a row with exactly k prime factors?Examples:
arr = [10005, 10030, 10026, 10008, 10016, 10028, 10004]
consec_kprimes(4, arr) => 3 because 10005 and 10030 are consecutive 4-primes, 10030 and >10026 too as well as 10028 and 10004 but 10008 and 10016 are 6-primes.consec_kprimes(4, [10175, 10185, 10180, 10197]) => 3 because 10175-10185 and 10185- >10180 and 10180-10197 are all consecutive 4-primes.
題目理解:當一個數num擁有k個質因數,則稱num為k質因數。設計一函式代入數字k與列表arr,返還列表arr中連續出現k質因數數的次數。
關於如何找出某數所擁有的質因數,可以參考我這篇Day23提到的方法,將其改為返還質因數的數量即可。
def first_divisor(num):
"""找到正整數num的1以外最小因數並返還"""
for n in range(2,int(num**0.5+1)):
if num % n == 0:
return n
#若在根號num範圍內無法找到因數,代表num本身為質數並返還num
return num
def kprimes(number):
"""找到正整數number所有的質因數"""
num = number
prime_divisor = []
while first_divisor(num) != num:
#將找到的最小因數加入prime_divisor並將num除去最小因數
#因為number為所有的prime_divisor相乘,故將num不斷除去找到到質因數直到num為止
prime_divisor.append(first_divisor(num))
num = num/first_divisor(num)
#則此時num為number的最後一個質因數
prime_divisor.append(int(num))
#最後返還質因數數量
return len(prime_divisor)
def consec_kprimes(k, arr):
"""找到arr中有多少組相鄰的元素為指定k質因數"""
lst_kprime = [kprimes(num) for num in arr ]
reslut = 0
consec = False
for i in lst_kprime:
#若找到符合k條件,但consec為False,表示為第一個符合條件的數
if i == k and consec == False:
consec = True
#直接進入下個循環看看下個數是否符合條件
continue
if i == k:
reslut += 1
else:
consec = False
return reslut